# Python 2.6.4
# Project Euler, Problem 95
# Copyright 2010 Talha Zaman

lim = 1000000
div = [0]*lim #sieving for divisor sums
for i in xrange(1,lim):
    for j in xrange(2*i, lim, i):
        div[j] += i

chain = [0]*lim #chains: -1 = bad, 0 = untested, n = length of chain
chain[0] = -1
for i in xrange(1,lim):
    if chain[i]: continue
    seq = [i]
    while(div[seq[-1]]<lim and chain[div[seq[-1]]]==0 and div[seq[-1]] not in seq):
        seq.append(div[seq[-1]])
    if div[seq[-1]] in seq: #hit a loop
        loop = seq.index(div[seq[-1]])
        for l in range(0, loop):
            chain[seq[l]] = -1 #pre-loop: mark as bad
        for l in range(loop, len(seq)):
            chain[seq[l]] = len(seq)-loop #within-loop: mark chain length
    else: #exceeded lim or hit a bad number
        for s in seq: chain[s] = -1 #mark as bad
print chain.index(max(chain))
